package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/cousins-in-binary-tree-ii/'>二叉树的堂兄弟节点 II(Cousins in Binary Tree II)</a>
 * <p>给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。</p>
 * <p>如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。</p>
 * <p>请你返回修改值之后，树的根 root 。</p>
 * <p>注意，一个节点的深度指的是从树根节点到这个节点经过的边数。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [5,4,9,1,10,null,7]
 *                      5                       0
 *                    /   \                   /   \
 *                   4     9        ==>      0     0
 *                 /  \      \             /  \     \
 *                1    10     7           7    7     11
 *      输出：[0,0,0,7,7,null,11]
 *      解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
 *          - 值为 5 的节点没有堂兄弟，所以值修改为 0 。
 *          - 值为 4 的节点没有堂兄弟，所以值修改为 0 。
 *          - 值为 9 的节点没有堂兄弟，所以值修改为 0 。
 *          - 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
 *          - 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
 *          - 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。
 *
 * 示例 2：
 *      输入：root = [3,1,2]
 *                      3                 0
 *                    /   \     ==>     /   \
 *                   1     2           0     0
 *      输出：[0,0,0]
 *      解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
 *          - 值为 3 的节点没有堂兄弟，所以值修改为 0 。
 *          - 值为 1 的节点没有堂兄弟，所以值修改为 0 。
 *          - 值为 2 的节点没有堂兄弟，所以值修改为 0 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中节点数目的范围是 [1, 10^5] 。</li>
 *         <li>1 <= Node.val <= 10^4</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0993CousinsInBinaryTree_S
 * @see LC2641CousinsInBinaryTree_II_M
 * @since 2024/2/29 15:26
 */
public class LC2641CousinsInBinaryTree_II_M {

    static class Solution {
        public TreeNode replaceValueInTree(TreeNode root) {
            Queue<TreeNode> currLevelNodeQueue = new ArrayDeque<>();
            currLevelNodeQueue.offer(root);
            root.val = 0;
            while (!currLevelNodeQueue.isEmpty()) {
                // nextLevelNodeValSum：下一次所有节点的和
                int nextLevelNodeValSum = 0;
                Queue<TreeNode> nextLevelNodeQueue = new ArrayDeque<>();
                for (TreeNode currLevelNode : currLevelNodeQueue) {
                    if (currLevelNode.left != null) {
                        nextLevelNodeQueue.add(currLevelNode.left);
                        nextLevelNodeValSum += currLevelNode.left.val;
                    }
                    if (currLevelNode.right != null) {
                        nextLevelNodeQueue.add(currLevelNode.right);
                        nextLevelNodeValSum += currLevelNode.right.val;
                    }
                }
                for (TreeNode currLevelNode : currLevelNodeQueue) {
                    // currNodeChildNodeValSum：当前节点子节点的和，左子节点+右子节点的和
                    int currNodeChildNodeValSum = (currLevelNode.left != null ? currLevelNode.left.val : 0) + (currLevelNode.right != null ? currLevelNode.right.val : 0);
                    // 下一层所有节点的和 - 当前节点的子节点的和：当前节点的子节点的堂兄弟的节点值之和；赋给当前节点的子节点
                    if (currLevelNode.left != null) {
                        currLevelNode.left.val = nextLevelNodeValSum - currNodeChildNodeValSum;
                    }
                    if (currLevelNode.right != null) {
                        currLevelNode.right.val = nextLevelNodeValSum - currNodeChildNodeValSum;
                    }
                }
                currLevelNodeQueue = nextLevelNodeQueue;
            }
            return root;
        }
    }

}
